package immutablecollections;

import immutablecollections.functions.*;
import immutablecollections.misc.*;
import java.util.*;

/**
 * An immutable version of `java.util.SortedSet`.
 * 
 * ### Introduction
 * 
 * <img src="doc-files/classes-focus-on-sortedset.png" alt="classes-focus-on-sortedset" style="width: 40em"/></p>
 * 
 */
public class ImSortedSet<T extends Comparable<? super T>> extends ImCollection<T>
{
    final ImTree<T> tree;

    @SuppressWarnings({ "unchecked", "rawtypes" })
    private static final ImSortedSet<?> empty = new ImSortedSet(ImTree.Nil());

    /**
     * The (singleton) empty set.
     * 
     *     
     */
    @SuppressWarnings("unchecked")
    public static <T extends Comparable<? super T>> ImSortedSet<T> empty()
    {
        return (ImSortedSet<T>) empty;
    }

    protected ImSortedSet(final ImTree<T> tree)
    {
        this.tree = tree;
    }

    /**
     * 
     */
    public static <A extends Comparable<A>> ImSortedSet<A> onArray(final A... array)
    {
        return onIterator(ArrayIterator.on(array));
    }

    public static <A extends Comparable<A>> ImSortedSet<A> onIterator(Iterator<A> iterator)
    {
        ImSortedSet<A> s = empty();

        while (iterator.hasNext())
        {
            s = s.adding(iterator.next());
        }

        return s;
    }

    @SuppressWarnings("unchecked")
    public static <A extends Comparable<? super A>> ImSortedSet<A> onAll(Collection<? extends A> elementsCollection)
    {
        if (elementsCollection instanceof ImSortedSet)
            return (ImSortedSet<A>) elementsCollection;
        else
        {
            // We tried to use on(Iterator) here but the type checking defeated us
            ImSortedSet<A> s = empty();
            for (A a : elementsCollection)
            {
                s = s.adding(a);
            }

            return s;
        }
    }

    public static <A extends Comparable<A>> ImSortedSet<A> on(A element)
    {
        return ImSortedSet.<A> empty().adding(element);
    }

    /**
     * Allows `ImSortedSet<U>` to be cast to `ImSortedSet<T>` (where U is a subtype of T) without generating a compiler warning.
     * 
     * For a detailed description see {@link ImList#upCast()}
     */
    @SuppressWarnings("unchecked")
    public <U extends Comparable<U>> ImSortedSet<U> upCast()
    {
        return (ImSortedSet<U>) this;
    }

    /**
     * Add `elementToAdd` to the set.
     * 
     * The set which contains the same elements as `this` and also contains `elementToAdd`.
     * 
     * If an *equal* element is already in this set then a new set will not be created - instead
     * `this` will be returned.
     */
    public ImSortedSet<T> adding(final T elementToAdd)
    {
        return new ImSortedSet<T>(add(tree, elementToAdd));
    }

    /**
     * Remove `elementToRemove` from the set.
     * 
     * The set which contains the same elements as `this` but does not contain `elementToRemove`.
     * 
     * If `elementToRemove` is not in the set then a new set will not be created - instead
     * `this` will be returned.
     */
    public ImSortedSet<T> remove(final T elementToRemove)
    {
        return new ImSortedSet<T>(remove(tree, elementToRemove));
    }

    /**
     * If an element that *equals* `elementToFind` is in the set then return it else return `null`.
     * 
     */
    public T find(final T elementToFind)
    {
        final ImTree<T> found = find(tree, elementToFind);

        return (found == ImTree.nil)
                ? null
                : found.getElement();
    }

    /**
     * A string representation of `this`.
     */
    @Override
    public String toString()
    {
        return "[" + TextUtils.join(iterator(), ", ") + "]";
    }

    /**
     * The number of elements in `this`.
     */
    public int size()
    {
        return tree.size();
    }

    // This version of the method is the one I would prefer to use. See the other version below
    //     public static <A extends Comparable<A>> ImTree<A> find1(final ImTree<A> tree, final A elementToFind)
    //     {
    //          if (tree == ImTree.nil)
    //               return tree;
    //
    //          final int order = elementToFind.compareTo(tree.element);
    //
    //          return order == 0
    //                    ? tree
    //                    : order < 0
    //                              ? find(tree.left, elementToFind)
    //                              : find(tree.right, elementToFind);
    //     }

    /**
     * If an element that *equals* `elementToFind` is in the set then return it else return `null`.
     * 
     */
    public static <A extends Comparable<? super A>> ImTree<A> find(ImTree<A> tree, final A elementToFind)
    {
        // I would prefer to have a recursive method here but I can squeeze a tiny bit of extra
        // performance out of this by not recursing so...
        while (true)
        {
            if (tree == ImTree.nil)
                return tree;

            int order = elementToFind.compareTo(tree.getElement());

            if (order == 0)
                return tree;

            tree = order < 0
                    ? tree.getLeft()
                    : tree.getRight();
        }
    }

    private static <A extends Comparable<? super A>> ImTree<A> add(final ImTree<A> tree, final A elementToAdd)
    {
        if (tree == ImTree.nil)
            return ImTree.newLeaf(elementToAdd);

        final int order = elementToAdd.compareTo(tree.getElement());

        return order == 0
                ? ImTree.newBalancedTree(elementToAdd, tree.getLeft(), tree.getRight())
                : order < 0
                        ? ImTree.newBalancedTree(tree.getElement(), add(tree.getLeft(), elementToAdd), tree.getRight())
                        : ImTree.newBalancedTree(tree.getElement(), tree.getLeft(), add(tree.getRight(), elementToAdd));
    }

    private static <A extends Comparable<? super A>> ImTree<A> remove(final ImTree<A> tree, final A elementToRemove)
    {
        return ImTreeZipper.find(ImTreeZipper.onRoot(tree), elementToRemove).removeNode().close();
    }

    /**
     * An iterator over the elements in `this`.
     *
     * Note that the iterator returned by this method will throw an
     * `UnsupportedOperationException` in response to its
     * `remove` method.
     *
     */
    public ImTreeIterator<T> iterator()
    {
        return new ImTreeIterator<T>(tree);
    }

    /**
     * `true` if `this` contains `elementToLookFor`.
     * 
     * More formally, returns `true` if and only if `this` contains
     * at least one element `e` such that
     * 
     *     e.equals(elementToLookFor)
     *
     */
    @SuppressWarnings("unchecked")
    @Override
    public boolean contains(Object object)
    {
        return find((T) object) != null;
    }

    /** 
     * Compares `other` with `this` for equality.
     * Returns `true` if and only if the specified object is also an `ImSortedSet`, both
     * SortedSets have the same size, and:
     * 
     *     this.containsAll(other)
     * 
     * In other words, two SortedSets are defined to be
     * *equal* if they contain *equal* elements.
     * 
     * In *other* other words - this is very similar to the standard Java SortedSet `equals`.
     *
     */
    @SuppressWarnings("rawtypes")
    @Override
    public boolean equals(Object other)
    {
        return this == other
                ? true
                : other instanceof ImSortedSet
                        ? eq((ImSortedSet) other)
                        : false;
    }

    private boolean eq(ImSortedSet<?> otherSortedSet)
    {
        return size() == otherSortedSet.size() && hashCode() == otherSortedSet.hashCode()
                ? elementsEq(iterator(), otherSortedSet.iterator())
                : false;
    }

    private boolean elementsEq(ImTreeIterator<?> itOne, ImTreeIterator<?> itTwo)
    {
        while (itOne.hasNext())
        {
            if (!itOne.next().equals(itTwo.next()))
                return false;
        }

        return true;
    }

    @Override
    public int hashCode()
    {
        return tree.hashCode();
    }

    public <O extends Comparable<O>> ImCollection<O> map(Function1<O> fn)
    {
        ImSortedSet<O> result = ImSortedSet.empty();

        for (T thing : this)
        {
            result = result.adding(fn.invoke(thing));
        }

        return result;
    }

    public ImSortedSet<T> addingAll(Collection<? extends T> elementsToAdd)
    {
        ImSortedSet<T> result = this;

        for (T a : elementsToAdd)
        {
            result = result.adding(a);
        }

        return result;
    }

    /**
     * The ImSortedSet formed out of the elements of each collection in `collections` in order.
     * 
     * ImCollections can't contain `null` so none of the elements can be `null`
     * 
     * ### Examples:
     * 
     *     List<Number> threeFive = Arrays.<Number> asList(3, 5);
     *     ImSortedSet<Integer> oneTwo = ImSortedSet.on(1, 2);
     * 
     *     joinArray(oneTwo, threeFive)          =>  [1, 2, 3, 5]");
     *     joinArray(oneTwo, threeFive, oneTwo)  =>  [1, 2, 3, 5, 1, 2]
     *     joinArray(on(), on())                 =>  []
     * 
     * @see #addingAll(Collection)
     * @see #joinIterator(Iterator)
     * @see #join(Collection)
     */
    public static <A extends Comparable<A>> ImSortedSet<A> joinArray(Collection<? extends A>... collections)
    {
        return joinIterator(ArrayIterator.on(collections));
    }

    /**
     * The ImSortedSet formed out of the elements of each collection in `iterator` in order.
     * 
     * ImCollections can't contain `null` so none of the elements can be `null`
     * 
     * @see #addingAll(Collection)
     * @see #joinArray(Collection...)
     * @see #join(Collection)
     */
    public static <A extends Comparable<A>> ImSortedSet<A> joinIterator(Iterator<Collection<? extends A>> iterator)
    {
        ImSortedSet<A> concat = ImSortedSet.empty();

        while (iterator.hasNext())
            concat = concat.addingAll(ImSortedSet.onAll(iterator.next()));

        return concat;
    }

    /**
     * The ImSortedSet formed out of the elements of each collection in `collectionOfCollections` in order.
     * 
     * ImCollections can't contain `null` so none of the elements can be `null`
     * 
     * @see #addingAll(Collection)
     * @see #joinArray(Collection...)
     * @see #joinIterator(Iterator)
     */
    public static <A extends Comparable<A>> ImSortedSet<A> join(
            Collection<? extends Collection<? extends A>> collectionOfCollections)
    {
        return joinIterator((Iterator<Collection<? extends A>>) collectionOfCollections.iterator());
    }

}